package practise.alogrithm.introductionToAlogrithm.foundations;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * a complete insert sorting
 */
public class InsertSorting {
    public static List<Integer> insertSorting(List<Integer> arrays){
        for(int i=1;i<arrays.size();i++){
            int current = arrays.get(i);
            int index=i;
            for(int j=i-1; j>=0 ; j--){// in this loop we will find a proper space for inserting the current value, if the current value is less than the value in the array, then it will go back
                // then there will be the space for inserting that number
                if(current<arrays.get(j)){
                    arrays.set(j+1,arrays.get(j));
                    index--;
                }
            }
            arrays.set(index,current);
        }

        return arrays;
    }

    public static void main(String[] args){
        List<Integer> array = new ArrayList<>(Arrays.asList(new Integer[]{1, 3, 2, 5, 4, 6, 7, 8, 0, 9,}));
        for(Integer value: insertSorting(array))
            System.out.print("["+value+"]");
    }
}
